﻿#include <iostream>
//#include "AbstractClass.h"
//#include "LineTable.h"
//#include "AloneLinkLhNode.h"
//#include "CirculateLinkNode.h"
//#include "DoubleLinkNode.h"
#include "StackClass.h"
#include "QueueClass.h"
#include "Array.h"
#include "Tree.h"
#include "GraphOperate.h"
#include "FindOperate.h"
#include "MySort.h"
#include "MyString.h"
#include <ctype.h>
#include <string.h>

using namespace std;
#pragma region 方法声明
//验证括号是否合法
bool checkBracket(char* express, int size);
void queueOperate();
void circulateQueueOperate();
int calculateAfterExpress(char* express, int size);
char* getMiddleExpress(char* express, int size);
int getPriority(char currentChar);
int getValidLength(char* express, int size);
void arrayOperate();
int findMax(int* arrays, const int size, int currentIndex);
int getMaxMod(int x, int y);
#pragma endregion

int main() {
#pragma region 顺序线性表
	//lineOperate();
#pragma endregion

#pragma region 单向链表
//aloneLinkOperate();
#pragma endregion

#pragma region 双向链表
//doubleLinkOperate();
#pragma endregion

#pragma region 循环链表
//circulateLinkOperate();
#pragma endregion

#pragma region 入栈-出栈-打印栈
//StackClass<char> stackClass(10);
//for (int i = 0; i < 10; i++)
//{
//	stackClass.push('a' + i);
//}
//for (int i = 0; i < 10; i++)
//{
//	stackClass.push('a' + i);
//}
//char popChar = stackClass.pop();
//if (popChar != NULL) {
//	std::cout << "成功出堆：" << popChar << std::endl;
//}
//std::cout << "堆长度为：" << stackClass.getPoint() << std::endl;
//stackClass.print();
#pragma endregion

#pragma region 验证括号是否合法
//char express[] = "(a + b) * a - ((45 - b) * (45 + 3))";
//char express[] = "(a + b) * a";
//const int len = sizeof(express) / sizeof(express[0]);
//cout << "括号" << (checkBracket(express, len) ? "" : "不") << "合法!" << endl;
#pragma endregion

#pragma region 队列应用
	//queueOperate();
#pragma endregion

#pragma region 使用中缀表达式转成后缀表达式，再根据后缀表达式计算出结果
	//char express[] = "(3 + 6) * 2 + 1";
	////36+2*1+
	////求得由字符串组成的中缀表达式转成的数组长度
	//int len = sizeof(express) / sizeof(char) - 1;
	////先验证中缀表达式的括号规则是否合法
	//if (checkBracket(express, len)) {
	//	//中缀表达式转成后缀表达式
	//	char *result = getMiddleExpress(express, len);
	//	cout << "中缀表达式：" << express << endl;
	//	cout << "后缀表达式：";
	//	//得到除去括号和空格后的中缀表达式长度
	//	const int myLen = getValidLength(express, len);
	//	for (int i = 0; i < myLen; i++)
	//	{
	//		cout << result[i];
	//	}
	//	cout << endl;
	//	//根据后缀表达式计算出结果
	//	const int value = calculateAfterExpress(result, myLen);
	//	cout << "计算结果为：" << value << endl;
	//}
	//else {
	//	cout << "表达式括号规则不合法：" << express << endl;
	//}
#pragma endregion

#pragma region 循环队列应用
	//circulateQueueOperate();
#pragma endregion

#pragma region 顺序串应用
	//sequencStringOperate();
#pragma endregion

#pragma region 数组应用
	//arrayOperate();
#pragma endregion

#pragma region 二叉树应用
	//true：堆栈模式、false:递归模式
	//const bool isStack = true;
	//TreeOperate<char> treeOperate;
	//treeOperate.ergodicTreeNode(isStack);
#pragma endregion

#pragma region 用递归求出数组中的最大值
	//int arrays[] = { 23,445,566,76,78,1,2,4,-56,1001 };
	//const int size = sizeof(arrays)/sizeof(int);
	//const int index = 0;
	//cout << "最大值：" << findMax(arrays, size, index) << endl;

	//TreeOperate<int> treeOperate;
	//treeOperate.findTree();
#pragma endregion

#pragma region 图-邻接矩阵
	//short direction = 0;//0:无向，1：有向，2：赋权
	//int size = 5;
	//GraphOperate graphOperate;
	//cout << endl << "无向图:" << endl;
	//AdjMaxtrix* twoNoDirections = graphOperate.CreateMaxtrixGraph(size, direction);
	//graphOperate.PrintMaxtrixGraph(*twoNoDirections, size);

	//direction = 1;
	//size = 4;
	//cout << endl << "有向图:" << endl;
	//AdjMaxtrix* twoDirections = graphOperate.CreateMaxtrixGraph(size, direction);
	//graphOperate.PrintMaxtrixGraph(*twoDirections, size);

	//direction = 2;
	//size = 6;
	//cout << endl << "赋权图:" << endl;
	//AdjMaxtrix* authorityDirections = graphOperate.CreateMaxtrixGraph(size, direction);
	//graphOperate.PrintMaxtrixGraph(*authorityDirections, size);

	//const int nodeCount = 5;
	//cout << endl << "邻接链表图:" << endl;
	//Graph2 g = graphOperate.CreateLinkGraph(nodeCount, 5);
	//graphOperate.iniVisted(nodeCount);
	//const int firstNodeIndex = 2;
	//if (firstNodeIndex < nodeCount) {
	//	cout << "从表结点[" << g.headNodes[firstNodeIndex].data << "]开始进行-递归方式-深度优先DFS遍历" << endl;
	//	graphOperate.Dfs(g, firstNodeIndex);
	//	cout << endl;

	//	graphOperate.iniVisted(nodeCount);
	//	cout << "开始进行-堆栈方式-深度优先DFS遍历" << endl;
	//	graphOperate.DfsStack(g, firstNodeIndex);
	//	cout << endl;
	//}
	//else {
	//	cout << "起点位置必须小于" << firstNodeIndex << endl;
	//}

	//graphOperate.iniVisted(nodeCount);
	//cout << "从表结点[" << g.headNodes[0].data << "]开始进行广度优先BFS遍历" << endl;
	//graphOperate.Bfs(g);
	//cout << endl;
#pragma endregion

#pragma region 查找算法
	//FindOperate findOperate;
	//int arrays[] = { 1,5,23,45,67,32,35,8 };
	////计算出数组长度
	//const int arraySize = sizeof(arrays) / sizeof(int);
	//cout << endl << "数组如下:" << endl;
	//for (size_t i = 0; i < arraySize; i++)
	//	cout << i << ":" << arrays[i] << endl;

	////目标数据
	//const int targetData = 8;
	//cout << endl << "顺序查找:";
	//int site = findOperate.orderFindTarget(arrays, arraySize, targetData);
	//findOperate.printResult(site, targetData);

	//MySort<int> mysort;
	////使用快速排序法，将数组升序排序
	//mysort.fastSort(0, arraySize - 1, arrays);
	//cout << endl << "排序后的数组如下:" << endl;
	//for (size_t i = 0; i < arraySize; i++)
	//	cout << i << ":" << arrays[i] << endl;

	//cout << endl << "折半查找（非递归）,前提条件是数组内的元素是有序的:";
	//site = findOperate.dichotomyFindTarget(arrays, 0, arraySize - 1, targetData);
	//findOperate.printResult(site, targetData);

	//cout << endl << "折半查找（递归）,前提条件是数组内的元素是有序的:";
	//site = findOperate.dichotomyRecursionTarget(arrays, 0, arraySize - 1, targetData);
	//findOperate.printResult(site, targetData);

	//cout << endl << "哈希表:";
	//int hashArrays[] = { 47,34,19,12,52,38,33,57,63};
	//const int hashArraySize = sizeof(hashArrays) / sizeof(int);
	//HashLinkNode * hashAddress = findOperate.createHashLinkTable(hashArrays, hashArraySize);
	//cout << endl << "哈希造表--链地址法:";
	//findOperate.printHashLinkTable(hashAddress, hashArraySize);
	//const int findKey = 34;
	//bool finder = findOperate.searchHashLink(hashAddress, hashArraySize, findKey);
	//cout << endl << "值[" << findKey << "]," << (finder ? "找到了！" : "未找到") << endl;

#pragma region 梁昊写的二叉查找算法
	//cout << endl << "梁昊写的二叉查找算法:" << endl;
	//int bsTArrays[] = { 23,445,566,76,78,1,2,4,-56,100 };
	//const int bsTSize = sizeof(bsTArrays) / sizeof(int);
	//TreeOperate<int> treeOpearte;
	//Node<int>* rootFindTree = treeOpearte.createFindTree(bsTArrays, bsTSize);
	////递归模式：中序遍历:左、根、右
	//treeOpearte.leftRootRigth(rootFindTree);
	//const int findValue = 566;
	//Node<int>* resultNode = treeOpearte.searchTree(rootFindTree, findValue);
	//cout << endl << "值[" << findValue << "]," << (resultNode ? "找到了！" : "未找到") << endl;
#pragma endregion

#pragma endregion

#pragma region 最大公约数
	//int m = 10, n = 6;
	//cout << endl << m << "与" << n << "的最大公约数是：" << getMaxMod(m, n) << endl;
#pragma endregion

#pragma region 排序
	//MySort<int> mySort;
	//int insertArray[] = { 11,2,3,4,8,5,6,70 };
	//const int insertSize = sizeof(insertArray) / sizeof(int);
	//cout << endl << "直接插入排序原始数组为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < insertSize; i++)
	//{
	//	cout << "[" << i << "]:" << insertArray[i] << " ";
	//}
	//cout << endl;
	//cout << endl << "直接插入排序过程为：" << endl;
	//mySort.insertSort(insertArray, insertSize);
	//cout << endl << "直接插入排序（时间复杂度为N的二次方），其结果为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < insertSize; i++)
	//{
	//	cout << "[" << i << "]:" << insertArray[i] << " ";
	//}
	//cout << endl;

	//int bubbleArray[] = { 11,2,3,4,8,5,6,70 };
	//const int bubbleSize = sizeof(bubbleArray) / sizeof(int);
	//cout << endl << "冒泡排序原始数组为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < bubbleSize; i++)
	//{
	//	cout << "[" << i << "]:" << bubbleArray[i] << " ";
	//}
	//cout << endl;
	//cout << endl << "冒泡排序过程为：" << endl;
	//mySort.bubbleSort(bubbleArray, bubbleSize);
	//cout << endl << "冒泡插入排序（时间复杂度为N的二次方），其结果为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < bubbleSize; i++)
	//{
	//	cout << "[" << i << "]:" << bubbleArray[i] << " ";
	//}
	//cout << endl;

	//int selectArray[] = { 11,2,3,4,8,5,6,70 };
	//const int selectSize = sizeof(selectArray) / sizeof(int);
	//cout << endl << "简单排序原始数组为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < selectSize; i++)
	//{
	//	cout << "[" << i << "]:" << selectArray[i] << " ";
	//}
	//cout << endl;
	//cout << endl << "简单排序过程为：" << endl;
	//mySort.selectSort(selectArray, selectSize);
	//cout << endl << "简单插入排序（时间复杂度为N的二次方），其结果为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < selectSize; i++)
	//{
	//	cout << "[" << i << "]:" << selectArray[i] << " ";
	//}
	//cout << endl;

	//int shellArray[] = { 11,2,3,4,8,5,6,70 };
	//const int shellSize = sizeof(shellArray) / sizeof(int);
	//cout << endl << "希尔排序原始数组为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < shellSize; i++)
	//{
	//	cout << "[" << i << "]:" << shellArray[i] << " ";
	//}
	//cout << endl;
	//mySort.shellSort(shellArray, shellSize);
	//cout << endl << "希尔插入排序（时间复杂度为N的1.3次方），其结果为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < shellSize; i++)
	//{
	//	cout << "[" << i << "]:" << shellArray[i] << " ";
	//}
	//cout << endl;

	//int quickArray[] = { 11,2,3,4,8,5,6,70 };
	//const int quickSize = sizeof(quickArray) / sizeof(int);
	//cout << endl << "快速排序原始数组为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < quickSize; i++)
	//{
	//	cout << "[" << i << "]:" << quickArray[i] << " ";
	//}
	//cout << endl;
	//mySort.quickSort(quickArray, 0, quickSize - 1);
	//cout << endl << "快速插入排序（时间复杂度为N * LOG 2 N），其结果为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < quickSize; i++)
	//{
	//	cout << "[" << i << "]:" << quickArray[i] << " ";
	//}
	//cout << endl;

	//int mergeArray[] = { 11,2,3,4,8,5,6,70 };
	//const int mergeSize = sizeof(mergeArray) / sizeof(int);
	//cout << endl << "归并排序原始数组为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < mergeSize; i++)
	//{
	//	cout << "[" << i << "]:" << mergeArray[i] << " ";
	//}
	//cout << endl;
	//mySort.mergeSort(mergeArray, 0, mergeSize - 1);
	//cout << endl << "归并插入排序（时间复杂度为N * LOG 2 N），其结果为：" << endl;
	//cout << "       ";
	//for (size_t i = 0; i < mergeSize; i++)
	//{
	//	cout << "[" << i << "]:" << mergeArray[i] << " ";
	//}
	//cout << endl;
#pragma endregion

#pragma region 字符串基础算法
	MyString myString;
	//主串
	string sourceString = "a0002asda";

	char modelArray[] = "0002";
	size_t inst = sourceString.length();

	char* targetArray = new char[inst];
	char* sourceArray = new char[inst];
	int index = 0;
	while (sourceString[index] != '\0') {
		sourceArray[index] = sourceString[index];
		index++;
	}
	sourceArray[index] = '\0';

	cout << endl << "字符串基础算法：" << endl << "  字符串长度：" << myString.strLen(sourceArray) << endl;
	cout << "  开始复制字符串至targetArray" << endl;
	myString.strCopy(targetArray, sourceArray);
	cout << "  比较结果：" << (myString.strCompare(targetArray, sourceArray) ? "" : "不") << "相等" << endl;
	cout << "  模式匹配结果：" << (myString.index(sourceArray, modelArray, 0) == 1 ? "成功" : "失败") << endl;
#pragma endregion

}
int getMaxMod(int m, int n) {
	int result = 0;
	int r = m % n;
	if (r != 0) {
		while (r != 0) {
			m = n;
			n = r;
			r = m % n;
			result = n;
		}
	}
	else {
		result = n;
	}
	return result;
}
#pragma region 数组应用
void arrayOperate() {
	//const int size = 10;
	const int row = 4;
	const int column = 6;
	Array myArray;
	//myArray.oneDimensionalArray(size);
	//myArray.twoDimensionalArray(row, column);

	myArray.threeDimensionalArray(4, 3, 3);
}
//递归找出数组中的最大数
//arrays:数组指针
//size:数组长度
//currentIndex:当前序号
int findMax(int* arrays, const int size, int currentIndex)
{
	int maxNumber;
	if (currentIndex > -1 && currentIndex < size) {
		//当前数
		int currentData = arrays[currentIndex];
		//下一个数
		int lastData = findMax(arrays, size, currentIndex + 1);
		maxNumber = currentData < lastData ? currentData : lastData;
	}
	else
		maxNumber = arrays[0];
	return maxNumber;
}

#pragma endregion

#pragma region 得到运算符及括号的优先级
int getPriority(char currentChar) {
	int priority;
	//乘法、除法的优先级最高，为2
	//加法、减法的优先级其次，为1
	//正括号的优先级最低，为0
	switch (currentChar)
	{
	case '*':
	case '/':
		priority = 2;
		break;
	case '+':
	case '-':
		priority = 1;
		break;
	case '(':
		priority = 0;
		break;
	default:
		priority = -1;
		break;
	}
	return priority;
}
#pragma endregion

#pragma region 得到除去括号后的表达式长度
int getValidLength(char* express, int size) {
	int len = 0;
	for (int i = 0; i < size; i++)
	{
		char currentChar = express[i];
		if (currentChar == '(' || currentChar == ')' || currentChar == ' ')
			continue;
		len++;
	}
	//size - 括号数量 - 空格数量
	return len;
}
#pragma endregion

#pragma region 使用中缀表达式得到后缀表达式
//参考：https://www.jb51.net/article/241710.htm
char* getMiddleExpress(char* express, int size) {
	const int myLen = getValidLength(express, size);
	char* results = new char[myLen];
	StackClass<char> stackClass(myLen);
	int index = 0;
	for (int i = 0; i < size; i++)
	{
		char currentChar = express[i];
		//空格，不参与输出
		if (currentChar == ' ')
			continue;
		//逻辑一：若是数字，直接输入到结果
		if (isdigit(currentChar)) {
			results[index++] = currentChar;
			cout << endl << "当前字符：" << currentChar << "，当前输出：";
			for (int i = 0; i < index; i++)
			{
				cout << results[i];
			}
			cout << endl;
		}
		//逻辑二：若是正括号，直接入栈
		else if (currentChar == '(') {
			stackClass.push(currentChar);
			cout << endl << "当前字符：" << currentChar << "，当前堆栈：" << endl;
			stackClass.print();
		}
		//逻辑三：若是反括号，一直出栈，止到栈顶元素为正括号为止
		else if (currentChar == ')') {
			char popChar = stackClass.peek();
			while (!stackClass.isEmpty() && popChar != '(') {
				popChar = stackClass.pop();
				if (popChar != '(')
					results[index++] = popChar;
			}
			cout << endl << "当前字符：" << currentChar << "，当前堆栈：" << endl;
			stackClass.print();
		}
		else {
			//逻辑四
			//若是加、减、乘、除的运算符，先比较运算符优先级
			//若当前运算符的优先级小于栈顶元素的优先级，则一直出栈至输出结果
			while (!stackClass.isEmpty() && getPriority(currentChar) <= getPriority(stackClass.peek())) {
				results[index++] = stackClass.pop();
			}
			//入栈当前运算符
			stackClass.push(currentChar);
			cout << endl << "当前字符：" << currentChar << "，当前堆栈：" << endl;
			stackClass.print();
			cout << "当前输出：";
			for (int i = 0; i < index; i++)
			{
				cout << results[i];
			}
			cout << endl;
		}
	}
	cout << endl << "最后堆栈：" << endl;
	stackClass.print();
	//逻辑五：若堆栈不为空，一直出栈，到堆空为止
	while (!stackClass.isEmpty()) {
		results[index++] = stackClass.pop();
	}
	cout << endl;
	return results;
}
#pragma endregion

#pragma region 使用后缀表达式计算出结果
int calculateAfterExpress(char* express, int size) {
	StackClass<int> stackClass(size);
	const int differNumber = 48;
	int x1, x2 = 0;

	for (int i = 0; i < size; i++)
	{
		char currentChar = express[i];
		//判断是否为数字
		if (isdigit(currentChar)) {
			//入栈
			stackClass.push(currentChar - differNumber);
		}
		else {
			x2 = stackClass.pop();
			x1 = stackClass.pop();
			switch (currentChar)
			{
			case '+':
				x1 += x2;
				break;
			case '-':
				x1 -= x2;
				break;
			case '*':
				x1 *= x2;
				break;
			case '/':
				if (x2 == 0) {
					cout << "除数不能为零，出错！" << endl;
					exit(0);
				}
				else {
					x1 /= x2;
					break;
				}
			}
			//入栈
			stackClass.push(x1);
		}
	}
	//出栈
	return stackClass.pop();
}
#pragma endregion

#pragma region 循环队列应用
void circulateQueueOperate() {
	const int queueLen = 3;
	CirculateQueueClass<char> circulateQueueClass(queueLen);
	for (int i = 0; i < queueLen; i++)
	{
		const char newElement = 'a' + i;
		if (!circulateQueueClass.intoQueue('a' + i)) {
			cout << "元素:" << newElement << ", 入队失败!" << endl;
		}
	}
	cout << "打印队列：" << endl;
	circulateQueueClass.printQueue();
	cout << "出队:" << circulateQueueClass.outQueue() << ", 成功!" << endl;
	cout << "打印队列：" << endl;
	circulateQueueClass.printQueue();
	for (int i = 0; i < 3; i++)
	{
		const char newElement = 'h' + i;
		if (!circulateQueueClass.intoQueue(newElement)) {
			cout << "元素:" << newElement << ", 入队失败!" << endl;
		}
	}
	cout << "打印队列：" << endl;
	circulateQueueClass.printQueue();
}
#pragma endregion

#pragma region 队列应用
void queueOperate() {
	//队列最大长度
	const size_t queueSize = 3;
	//预入队数量
	const size_t dataCount = 5;
	QueueClass<int> queue(queueSize);
	for (size_t i = 0; i < dataCount; i++)
	{
		int data = i + 1;
		if (!queue.intoQueue(data))
			cout << "入值[" << data << "],由于队列已满，入队失败！" << endl;
	}
	cout << endl << "从头到尾打印" << endl;
	queue.printQueue();

	cout << endl << "队尾值:" << queue.getQueueRearValue() << endl;
	cout << endl << "开始出队" << endl;
	for (size_t i = 0; i < dataCount; i++)
	{
		int data = queue.outQueue();
		if (data != -1)
			cout << "出队" << i << ":" << data << endl;
		else
			cout << "出队：" << i << "失败!" << endl;
	}
}
#pragma endregion

#pragma region 验证括号是否合法
bool checkBracket(char* express, int size)
{
	StackClass<char> stackClass(size);
	bool state = true;
	for (size_t i = 0; i < size; i++)
	{
		char currentChar = express[i];
		if (currentChar == '(')
			stackClass.push(currentChar);
		if (currentChar == ')') {
			char popChar = stackClass.pop();
			if (popChar == NULL || popChar != '(')
				state = false;
		}

	}
	return state && stackClass.isEmpty();
}
#pragma endregion

